package com.algorithm.quick;/*
 *@Author:DOWN
 *@Date:2022/1/18 17:42
 *@Comment:快排-递归
 *         退化：有序、所有元素一样、partition middle
 */

import com.algorithm.testutils.ArrayGenerator;
import com.algorithm.testutils.SortingHelp;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    private static Random random = new Random();

    public static <E extends Comparable<E>> void sort(E[] arrs) {
        sort(arrs, 0, arrs.length - 1);
    }

    /**
     * 排序
     *
     * @param arrs 元素组
     * @param l    起点索引
     * @param r    终点索引
     * @param <E>  泛型
     */
    public static <E extends Comparable<E>> void sort(E[] arrs, int l, int r) {
        if (l >= r) {
            return;
        }
        //递归 从大区间->到小区间
        int midIndex = partition(arrs, l, r);
        sort(arrs, l, midIndex);
        sort(arrs, midIndex + 1, r);
    }

    /**
     * 《单路》
     * 分割区间返回中间索引
     *
     * @param arrs 元素组
     * @param l    起点索引
     * @param r    终点索引
     * @param <E>  泛型
     * @return middle index
     */
    public static <E extends Comparable<E>> int partition(E[] arrs, int l, int r) {
        //bound 不包含 range [0,n)
        int changeIndex = l + (random).nextInt(r - l + 1);
        swap(arrs, l, changeIndex);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arrs[i].compareTo(arrs[l]) < 0) {
                j++;
                swap(arrs, i, j);
            }
        }
        //交换正确 中点
        swap(arrs, l, j);
        return j;
    }

    public static <E extends Comparable<E>> void sortTwoWays(E[] arrs) {
        sortTwoWays(arrs, 0, arrs.length - 1);
    }

    /**
     * 排序
     *
     * @param arrs 元素组
     * @param l    起点索引
     * @param r    终点索引
     * @param <E>  泛型
     */
    public static <E extends Comparable<E>> void sortTwoWays(E[] arrs, int l, int r) {
        if (l >= r) {
            return;
        }
        //递归 从大区间->到小区间
        int midIndex = partitionTwoWays(arrs, l, r);
        sortTwoWays(arrs, l, midIndex);
        sortTwoWays(arrs, midIndex + 1, r);
    }

    /**
     * 《双路》
     * 分割区间 l开始、r开始，首尾两个区间，返回中间索引
     *
     * @param arrs 元素组
     * @param l    起点索引
     * @param r    终点索引
     * @param <E>  泛型
     * @return middle index
     */
    public static <E extends Comparable<E>> int partitionTwoWays(E[] arrs, int l, int r) {
        //bound 不包含 range [0,n)
        int changeIndex = l + (random).nextInt(r - l + 1);
        swap(arrs, l, changeIndex);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arrs[i].compareTo(arrs[l]) < 0) {
                i++;
            }
            while (j >= i && arrs[j].compareTo(arrs[l]) > 0) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arrs, l, j);
            i++;
            j--;
        }
        //交换正确 中点
        swap(arrs, l, j);
        return j;
    }

    /**
     * 三路
     * @param arrs 元素组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void sortThreeWays(E[] arrs) {
        sortThreeWays(arrs, 0, arrs.length - 1);
    }

    /**
     * 排序
     *
     * @param arrs 元素组
     * @param l    起点索引
     * @param r    终点索引
     * @param <E>  泛型
     */
    public static <E extends Comparable<E>> void sortThreeWays(E[] arrs, int l, int r) {
        if (l >= r) {
            return;
        }
        //递归 从大区间->到小区间
        int changeIndex = l + (random).nextInt(r - l + 1);
        swap(arrs, l, changeIndex);

        int lt = l, i = lt + 1, gt = r + 1;
        while (i < gt) {
            if (arrs[i].compareTo(arrs[l]) < 0) {
                lt++;
                swap(arrs, lt, i);
                i++;
            } else if (arrs[i].compareTo(arrs[l]) > 0) {
                gt--;
                swap(arrs, i, gt);
            } else {
                i++;
            }
        }
        swap(arrs, lt, l);
        sortThreeWays(arrs, l, lt - 1);
        sortThreeWays(arrs, gt, r);
    }

    /**
     * 交换位置
     *
     * @param arr 元素组
     * @param i   甲
     * @param j   乙
     * @param <E> 泛型
     */
    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) throws Exception {

        //Integer[] arr1 = ArrayGenerator.getArrays(10000000);
        Integer[] arr2 = ArrayGenerator.getArrays(10000000);

        //SortingHelp.sortTest("com.algorithm.merger.MergeSort", "sort", arr1);
        SortingHelp.sortTest("com.algorithm.quick.QuickSort", "sort", arr2);
        SortingHelp.sortTest("com.algorithm.quick.QuickSort", "sortTwoWays", arr2);
        SortingHelp.sortTest("com.algorithm.quick.QuickSort", "sortThreeWays", arr2);
    }
}
